package exercise02;

public class Day230702 {
    // 移动零
    public void moveZeroes(int[] nums) {
        int dest = -1;
        int cur = 0;
        for (;cur < nums.length; cur++) {
            if (nums[cur] != 0) {
                dest++;
                if (nums[dest] != 0) {
                    continue;
                }
                nums[dest] = nums[cur];
                nums[cur] = 0;
            }
        }
    }

    // 复写零
    public void duplicateZeros(int[] arr) {
        int n = arr.length; // 记录数组剩余空间
        int count = 0;      // 记录可以复写的零的个数
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] != 0) {
                // 非零占一个位置
                n--;
            } else {
                if (n < 2) {
                    break;
                }
                // 零需要复写, 占两个位置
                n -= 2;
                count++;
            }
        }
        int cur = arr.length - 1 - count;
        int dest = arr.length - 1;
        if (n == 1) {
            // 处理边界0, 没有空间复写的情况
            // 数组剩余空间为 1
            // 说明最后一个为0, 这个0不能被复写
            arr[dest] = 0;
            cur--;
            dest--;
        }
        // 双指针, 从右往左遍历
        for (;cur >= 0; cur--, dest--) {
            if (arr[cur] == 0) {
                // 复写零
                arr[dest] = 0;
                dest--;
                arr[dest]= 0;
            } else {
                arr[dest] = arr[cur];
            }
        }
    }

    public void duplicateZeros2(int[] arr) {
        int cur = 0;
        int dest = -1;
        int n = arr.length;
        while (cur < n) {
            if (arr[cur] == 0) {
                dest += 2;
            } else {
                dest += 1;
            }
            if (dest >= n - 1) break;
            cur++;
        }

        if (dest == n) {
            // 处理边界0, 没有空间复写的情况
            arr[n - 1] = 0;
            dest -= 2;
            cur--;
        }

        // 双指针, 从右往左遍历
        for (;cur >= 0; cur--, dest--) {
            if (arr[cur] == 0) {
                // 复写零
                arr[dest] = 0;
                dest--;
                arr[dest]= 0;
            } else {
                arr[dest] = arr[cur];
            }
        }
    }
}
